import java.util.ArrayList;
import java.util.List;

public class Solution22 {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        StringBuilder s = new StringBuilder();
        generate(res, s, 0, 0, n);
        return res;
    }

    private void generate(List<String> res, StringBuilder s, int left, int right, int n) {
        if (right > left || left > n)
            return;
        if (left + right == n * 2) {
            if (left == right) {
                res.add(String.valueOf(s));
            }
            return;
        }
        s.append('(');
        generate(res, s, left + 1, right, n);
        s.deleteCharAt(s.length() - 1);
        s.append(')');
        generate(res, s, left, right + 1, n);
        s.deleteCharAt(s.length() - 1);
    }
}
